The present invention relates to an encoding apparatus and an encoding method, and more particularly to an encoding apparatus and an encoding method which are capable of encoding supplied data into high-performance codes with a simple arrangement.
Linear codes for realizing an error correcting code technology using an algebraic process include, for example, quasi-cyclic codes and IRA (Irregular Repeat Accumulate) codes. A quasi-cyclic code having a code length n is a code whose parity-check matrix is expressed as a matrix having m×m cyclic square matrixes as elements where m represents a divisor of n.
FIG. 1 of the accompanying drawings shows an arrangement of a parity-check matrix HQC for quasi-cyclic codes for n=15 and m=5. In FIG. 1, the parity-check matrix HQC includes a 2 (rows)×3 (columns) matrix having 5×5 cyclic square matrixes as elements.
An encoding apparatus for encoding supplied data into quasi-cyclic codes having such a parity-check matrix can simply be constructed using shift registers. For example, R. L. Townsent, E. J. Weldon, Jr., “Self-Orthogonal Quasi-Cyclic Codes”, IEEE Transaction on Information Theory, Vol. IT-13, No. 2, April 1967 discloses quasi-cyclic codes on a finite field Fq having elements represented by a power of a prime number, expressed by a code length n, an information length k, and cyclic square matrixes having a size m, n=n0×m, k=k0×m, l:=(n−k)/m=n0−k0. In the quasi-cyclic codes, n0 and l represent the number of columns and the number of rows, respectively, of a parity-check matrix having m×m cyclic square matrixes as elements. In other words, if m elements are considered as a block, then n0, k0, and l represent a code length, an information length, and a parity number.
An IRA code having a code length n and an information length k is generally a code whose parity-check matrix includes an (n−k) information part where zero elements (e.g., 0) and nonzero elements (e.g., 1) are arranged in an arbitrary pattern and a k parity part where nonzero elements are arranged in a step-like pattern and zero elements are placed as remaining entries. IRA codes are known as high-performance codes in the art, as disclosed in H. Jin, A. Khandekar, R. J. McEliece, “Irregular Repeat-Accumulate Codes”, in Proc. 2nd International Symposium on Turbo Codes and Related Topics, Brest, France, PP. 1-8, September 2000.
FIG. 2 of the accompanying drawings shows an arrangement of a parity-check matrix HIRA for IRA codes for n=15, k=5. In FIG. 2, the parity-check matrix HIRA includes an information part 11 as a 10 (rows)×5 (columns) matrix and a parity part 12 as a 10 (rows)×10 (columns) matrix.
The parity-check matrix HIRA can be expressed using a Tanner graph shown in FIG. 3 of the accompanying drawings. In FIG. 3, solid circles represent variable nodes, and squares check nodes. The variable nodes correspond to the columns of the parity-check matrix HIRA. The parity-check matrix HIRA includes an information part 21 having (n−k) (5 in FIG. 3) variable nodes and a parity part 22 having k (10 in FIG. 3) variable nodes with degree 2 (the number of edges). The check nodes correspond to the rows of the parity-check matrix HIRA. The parity-check matrix HIRA has a check node part 23 having k (10 in FIG. 3) check nodes. The check nodes and the variable nodes are connected to each other by edges which correspond to the nonzero elements of the parity-check matrix HIRA.
An encoding apparatus for encoding supplied data into IRA codes having such a parity-check matrix will be described below with reference to FIG. 4 of the accompanying drawings. In FIG. 4, the encoding apparatus includes a puncture circuit 31, a random interleaver 32, and an accumulator 33.
The puncture circuit 31 withdraws input information bits according to predetermined rules, and supplies the withdrawn information bits as data to the random interleaver 32. The random interleaver 32 rearranges the data withdrawn by the puncture circuit 31, and supplies the rearranged data to the accumulator 33.
The accumulator 33 includes an arithmetic unit 41 and a shift register 42 having a plurality of memory elements. The arithmetic unit 41 adds the data from the random interleaver 32 and data supplied from the shift register 42 on a finite field F2, i.e., exclusive-ORs the data from the random interleaver 32 and data supplied from the shift register 42, and supplies the sum to the shift register 42. The shift register 42 stores the value supplied from the arithmetic unit 41, and supplies the stored value, i.e., the sum produced by the arithmetic unit 41 in a preceding cycle, to the arithmetic unit 41 and outputs the stored value to a following stage.
The encoding apparatus shown in FIG. 4 outputs a sequence of encoded bits which is a combination of the input data and the value output from the accumulator 33 as IRA-encoded input data to a communication path.
While high-performance codes are realized using IRA codes, the encoding apparatus for encoding supplied data into IRA codes is highly costly and complex in arrangement because it requires the random interleaver 32 that is expensive.
The encoding apparatus for encoding supplied data into quasi-cyclic codes is of a simple arrangement and can easily be implemented as it includes shift registers. However, since parity-check matrixes for IRA codes are not quasi-cyclic, the encoding apparatus for encoding supplied data into quasi-cyclic codes cannot be used to encode supplied data into high-performance codes such as IRA codes.